package sort.cmp;

/**
 * @Author kaho
 * @create 2020/11/29
 */
public class 插入排序 {


    public static void insertSort(int[] arr) {
        for (int begin = 1; begin < arr.length; begin++) {
            int cur = begin;
            int val = arr[cur];
            while (cur > 0 && arr[cur - 1] > val) {
                arr[cur] = arr[cur - 1];
                cur--;
            }
            arr[cur] = val;

        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{19, 14, 5, 7, 8, 1};
        insertSort1(arr);
    }


    /**
     * 使用二分搜索对插入排序进行优化
     * @param arr
     */
    public static void insertSort1(int[] arr) {
        for (int begin = 1; begin < arr.length; begin++) {
            int target = arr[begin];
            int idx = search(arr, target, begin - 1);
            for (int cur = begin; cur > idx; cur--) {
                arr[cur] = arr[cur -1];
            }
            arr[idx] = target;
        }
    }

    public static int search(int[] arr, int target, int end) {
        int start = 0;
        while (start < end) {
            int mid = start + ((end - start) >> 1);
            if (arr[mid] > target) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
}
